package leetcode.editor.cn;
//给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。 
//
// 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 
//
// 你可以假设 nums1 和 nums2 不会同时为空。 
//
// 
//
// 示例 1: 
//
// nums1 = [1, 3]
//nums2 = [2]
//
//则中位数是 2.0
// 
//
// 示例 2: 
//
// nums1 = [1, 2]
//nums2 = [3, 4]
//
//则中位数是 (2 + 3)/2 = 2.5
// 
// Related Topics 数组 二分查找 分治算法 
// 👍 3225 👎 0

import java.util.Arrays;

//Java：寻找两个正序数组的中位数
class P4MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        int[] arr1 = {1, 2};
        int[] arr2 = {1, 1};
        Solution solution = new P4MedianOfTwoSortedArrays().new Solution();
        double result = solution.findMedianSortedArrays(arr1, arr2);

        System.out.println("给定数组1" + Arrays.toString(arr1) + ",给定数组2" + Arrays.toString(arr2) + "中位数是：" + result);
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            double result = 0.00;

            //第一种方法开始
            // TODO Auto-generated method stub
            // int[] temp = new int[nums1.length + nums2.length];
            // int i = 0;
            // int j = 0;
            // int k = 0;
            // while (i < nums1.length && j < nums2.length) {
            //     temp[k++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
            // }
            // while (i < nums1.length) {
            //     temp[k++] = nums1[i++];
            // }
            // while (j < nums2.length) {
            //     temp[k++] = nums2[j++];
            // }
            // return temp.length % 2 == 1 ? temp[temp.length / 2] : ((double) temp[temp.length / 2] + temp[temp.length / 2 - 1]) / 2;
            //第一种方法结束

            //第二种方法开始

            /*---------以下是核心代码，对上面两个有序数组进行二路归并a*/
            int i = 0;
            int j = 0;
            int k = 0;
            int len = nums1.length + nums2.length;
            int[] arr = new int[len];
            while (i < nums1.length && j < nums2.length) {
                if (nums1[i] <= nums2[j]) {
                    arr[k++] = nums1[i++];
                } else {
                    arr[k++] = nums2[j++];
                }
            }
            if (i == nums1.length && j < nums2.length) {
                while (j < nums2.length) {
                    arr[k++] = nums2[j++];
                }
            }
            if (j == nums2.length && i < nums1.length) {
                while (i < nums1.length) {
                    arr[k++] = nums1[i++];
                }
            }
            result = arr.length % 2 == 1 ? arr[arr.length / 2] : ((double) arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2;
            //第二种方法结束
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}